package com.leetcode.binarySearch;

import java.util.Arrays;
import java.util.Scanner;

public class FindMedian {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int[] nums1 = new int[n];
            int[] nums2 = new int[m];
            for (int i = 0; i < n; i++) {
                nums1[i] = scanner.nextInt();
            }
            for (int j = 0; j < m; j++) {
                nums2[j] = scanner.nextInt();
            }
            System.out.println(solver2(nums1, nums2));
        }
    }

    public static double solver(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] nums = new int[n + m];
        // nums1和nums2数组都是从小到大的有序数组
        for (int i = 0, j = 0; i < n || j < m; ) {
            while (j < m && (i == n || nums1[i] > nums2[j])) {
                nums[i + j] = nums2[j];
                j++;
            }
            while (i < n && (j == m || nums1[i] <= nums2[j])) {
                nums[i + j] = nums1[i];
                i++;
            }
        }
        System.out.println(Arrays.toString(nums));
        int ind = (m + n) / 2;
        if (((m + n) & 1) == 1) {
            return nums[ind];
        } else {
            return (nums[ind - 1] + nums[ind]) / 2.0;
        }
    }

    public static double solver2(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int totalLen = len1 + len2;
        if (totalLen % 2 == 1) {
            int midIndex = totalLen / 2;
            return binarySearch(nums1, nums2, midIndex + 1);
        } else {
            int midIndex1 = totalLen / 2 - 1;
            int midIndex2 = totalLen / 2;
            return (binarySearch(nums1, nums2, midIndex1 + 1)
                    + binarySearch(nums1, nums2, midIndex2 + 1)) / 2.0;
        }
    }

    private static int binarySearch(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int index1 = 0;
        int index2 = 0;
        while(true) {
            // 边界情况
            if(index1 == len1) {
                return nums2[index2 + k - 1];
            }
            if(index2 == len2) {
                return nums1[index1 + k - 1];
            }
            if(k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, len1) - 1;
            int newIndex2 = Math.min(index2 + half, len2) - 1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if(pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}
